﻿/*141. 周期
一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 abaab 共有 5个前缀，分别是 a，ab，aba，abaa，abaab。
我们希望知道一个 N位字符串 S的前缀是否具有循环节。
换言之，对于每一个从头开始的长度为 i（i > 1的前缀，是否由重复出现的子串 A组成，即 AAA…A（A重复出现 K次, K > 1）。

如果存在，请找出最短的循环节对应的 K值（也就是这个前缀串的所有可能重复节中，最大的 K值）。

输入格式
输入包括多组测试数据，每组测试数据包括两行。
第一行输入字符串 S的长度 N
第二行输入字符串 S
输入数据以只包括一个 0的行作为结尾。

输出格式
对于每组测试数据，第一行输出 Test case # 和测试数据的编号。

接下来的每一行，输出具有循环节的前缀的长度 i和其对应 K，中间用一个空格隔开。
前缀长度需要升序排列。
在每组测试数据的最后输出一个空行。

数据范围
2≤N≤1000000
输入样例：
3
aaa
4
abcd
12
aabaabaabaab
0
输出样例：
Test case #1
2 2
3 3

Test case #2

Test case #3
2 2
6 2
9 3
12 4
*/

//周期
/*题目含义：
aabaabaabaab
Test case #3
2 2  --前缀为2的时候(aa),循环元(a)个数为2个
6 2  --前缀为6的时候(aabaab),循环元(aab)个数为2个
9 3  --前缀为2的时候(aabaabaab),循环元(aab)个数为3个
12 4  --前缀为2的时候(aabaabaabaab),循环元(aab)个数为4个*/
/*要做的工作：
1.计算前缀内，ne[]，然后计算个数*/
#include<iostream>
#include<stdio.h>
using namespace std;
const int N = 1000010;
int ne[N];
char s[N];

int main()
{
    int T = 1;
    int n, k;
    //cin>>n>>s;
    while (scanf("%d", &n), n)//输入n，循环n
    {
        cin >> s + 1;
        for (int i = 2, j = 0; i <= n; i++)
        {
            while (j && s[i] != s[j + 1])    j = ne[j];
            if (s[i] == s[j + 1])    j++;
            ne[i] = j;
        }
        cout << "Test case #" << T++ << endl;//输出T，T+1

        for (int i = 1; i <= n; i++) //i初始从1,不是0
        {
            int t = i - ne[i];//t:循环节长度
            if (i % t == 0 && i / t >= 2) //i/t:循环节的个数
                //这个里面不考虑吧ababc这样的情况，均是ababac i%t==0
                cout << i << ' ' << i / t << endl; //i:前缀长
        }
        puts("");//换行 
        //cout<<endl;一样
    }
}
/*kmp性质：若 i % (i - ne[i]) == 0
那么 s[1 ~ (i - ne[i])] 是 s[1 ~ i] 的最小循环元
而 i / (i - ne[i]) 是 它最大循环次数 K*/

/*一个疑问：
t=i-ne[i]是循环节的长度
在 a b a b a c这样的情况下，ne[3]=1,t=3-1=2，
但是明显当i=3时，aba循环节是a，t应该=1才对啊*/


/*总结：
1.eg: scanf("%d%d",&a,&b);
scanf的返回值是输入值的个数
　　①如果a和b都被成功读入，则scanf的返回值为2。
　　②如果只有a被成功读入，那么返回值为1。
　　③如果a和b都未被成功读入，那么返回值就为0。
　　④如果遇到错误或遇到end of file，返回值为EOF，EOF一般（不是标准）为-1。
————————————————
2.while(scanf("%d",&n),n) 《=》while(scanf("%d",&n)&&n)
返回值为1同时n的值不能为0
这个和while(n),while(1)还不一样，循环执行1次，每次都要再输入一次n
适用情况：n不是循环次数，需要多次输入n值，“输入数据以只包括一个 0的行作为结尾”最后输入0结尾

while(cin>>n &&1)这个就不对，因为输入n=0时，输入成功但是返回1，1&&1=》可以循环
————————————————
3.kmp性质：若 i % (i - ne[i]) == 0
那么 s[1 ~ (i - ne[i])] 是 s[1 ~ i] 的最小循环元
而 i / (i - ne[i]) 是 它最大循环次数 K
————————————————
4.*/